{\magonebf 6.6 Planar Subdivisions (subdivision)}

\decl subdivision I 

{\bf 1. Definition}

An instance $S$ of the parameterized data type \name\ is a 
subdivision of the two-dimensional plane, i.e., an embedded planar graph 
with straight line edges (see also sections 5.3 and 5.6). With each node 
$v$ of $S$ is associated a point, called the position of $v$ and with each 
face of $S$ is associated an information from data type $I$, called the 
information type of $S$.


{\bf 2. Creation}

\create S (GRAPH\<point,I\>\ G)

creates an instance \var\ of type \name\ and initializes it to 
the subdivision represented by the parameterized directed graph $G$. 
The node entries of $G$ (of type point)  define the positions of the 
corresponding nodes of \var. Every face $f$ of \var\ is assigned the 
information of one of its bounding edges in $G$.  \precond $G$ represents 
a planar subdivision, i.e., a straight line embedded planar map.


\bigskip
{\bf 2. Operations}
\medskip
\+\op point  position {node\ v}       
                                      { returns the position of node $v$.}
\smallskip
\+\op ftype  inf      {face\ f}       
                                      { returns the information of face $f$.}
\smallskip
\+\op face   locate\_point {point\ p} 
                                      { returns the face containing point $p$.}
\smallskip


\bigskip
{\bf 3. Implementation}

Planar subdivisions are implemented by parameterized planar maps and an
additional data structure for point location based on persistent search trees
([DSST89]). Operations position and inf take constant time, a locate\_point 
operation takes time $O(\log^2 n)$. Here $n$ is the number of nodes. 
The space requiremnt and the initialization time is $O(n^2)$.

